//给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。 
//
// 岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。 
//
// 此外，你可以假设该网格的四条边均被水包围。 
//
// 
//
// 示例 1： 
//
// 
//输入：grid = [
//  ["1","1","1","1","0"],
//  ["1","1","0","1","0"],
//  ["1","1","0","0","0"],
//  ["0","0","0","0","0"]
//]
//输出：1
// 
//
// 示例 2： 
//
// 
//输入：grid = [
//  ["1","1","0","0","0"],
//  ["1","1","0","0","0"],
//  ["0","0","1","0","0"],
//  ["0","0","0","1","1"]
//]
//输出：3
// 
//
// 
//
// 提示： 
//
// 
// m == grid.length 
// n == grid[i].length 
// 1 <= m, n <= 300 
// grid[i][j] 的值为 '0' 或 '1' 
// 
// Related Topics 深度优先搜索 广度优先搜索 并查集 数组 矩阵 
// 👍 1426 👎 0

package com.cute.leetcode.editor.cn;

import java.util.LinkedList;
import java.util.Queue;

public class NumberOfIslands {
    public static void main(String[] args) {
        char[][] grid = {{'1','1','0','0','0'},{'1','1','0','0','0'},{'0','0','1','0','0'},{'0','0','0','1','1'}};
        new NumberOfIslands().new Solution().numIslands(grid);
    }
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 一样使用的沉岛的思想（dfs）
         * 1.主方法中寻找岛屿的入口位置，每进入一次res++
         * 2.找到岛屿入口位置后，遍历所有可以访问到的岛屿，并且访问过就沉下去
         * 3.返回res
         *
         * 使用深度优先遍历可以实现的话，那么使用广度优先遍历借助队列依然可以实现
         */
        int row;
        int col;
        int[][] directions = {{1,0},{-1,0},{0,1},{0,-1}};
        public int numIslands(char[][] grid) {
            row = grid.length;
            col = grid[0].length;
            int res = 0;
            for (int i = 0; i < grid.length; i++) {
                for (int j = 0; j < grid[0].length; j++) {
                    if (grid[i][j] != '0'){//找到入口
                        res++;
                        bfs(i,j,grid);
                    }
                }
            }
            return res;
        }

        private void dfs(int i, int j, char[][] grid) {
            if (inGrid(i,j) && grid[i][j]!='0') {
                grid[i][j] = '0';//沉岛
                //遍历所有岛屿
                dfs(i+1,j,grid);
                dfs(i-1,j,grid);
                dfs(i,j+1,grid);
                dfs(i,j-1,grid);
            }
        }

        private boolean inGrid(int i, int j) {
            return i >= 0 && i < row && j >=0 && j <col;
        }

        /**
         * bfs进行岛屿的遍历
         * 使用队列储存坐标信息
         */
        public void bfs(int i, int j, char[][] grid){
            grid[i][j] = '0';
            Queue<int[]> queue = new LinkedList<>();
            queue.add(new int[]{i, j});
            while (!queue.isEmpty()){
                int x = queue.peek()[0];
                int y = queue.poll()[1];
                int newX;
                int newY;
                for (int[] d : directions){
                    newX = x + d[0];
                    newY = y + d[1];
                    if (inGrid(newX, newY)&&grid[newX][newY]!='0'){
                        grid[newX][newY] = '0';
                        queue.add(new int[]{newX, newY});
                    }
                }

            }

        }

    }
//leetcode submit region end(Prohibit modification and deletion)

}